﻿#define _CRT_SECURE_NO_WARNINGS


#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//struct TreeNode 
//{
//	int val;
//	struct TreeNode* left;
//	struct TreeNode* right;
//};


//单值二叉树

//如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
//只有给定的树是单值二叉树时，才返回 true；否则返回 false。
//原理：a==b,b==c => a==c
//bool isUnivalTree(struct TreeNode* root)
//{
//	if (root == NULL)
//		return true;
//	if (root->left && root->left->val != root->val)//若左孩子为空或左孩子的值与根不相等，则无须继续比较
//		return false;
//	if (root->right && root->right->val != root->val)//同理
//		return false;
//
//	return isUnivalTree(root->left) && isUnivalTree(root->right);//递归，让每个根与其左右孩子分别去比较
//}


//相同的树

//给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
//如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
//{
//	//p q都为空
//	if (p == NULL && q == NULL)
//		return true;
//
//	//p q其中一个为空
////	if ((p == NULL && q != NULL) || (p != NULL && q == NULL))
//	if(p==NULL || q==NULL)//只要其中一个不为空就不相等
//		return false;
//
//	//p q都不为空
//	if (p->val != q->val)
//		return false;
//
//	//p q相等
//	//继续分别比较左右子树
//	return isSameTree(p->left, q->left)
//		&& isSameTree(p->right, q->right);
//}

// *
//二叉树的前序遍历

//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
//返回类型为整型数组
//Note: The returned array must be malloced, assume caller calls free().
//int TreeSize(struct TreeNode* root)
//{
//	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//void preorder(struct TreeNode* root, int* a, int* pi)
//{
//	if (root == NULL)
//		return;
//	a[(*pi)++] = root->val;
//	preorder(root->left, a, pi);
//	preorder(root->right, a, pi);
//}
//
//int* preorderTraversal(struct TreeNode* root, int* returnSize)
//{
//	//用malloc开辟空间，将递归申请的空间从栈移到堆上
//	//int* a = (int*)malloc(sizeof(int) * TreeSize(root));
//	//*returnSize = TreeSize(root);
//		
//	*returnSize = TreeSize(root);
//	int* a = (int*)malloc(sizeof(int) * (*returnSize));
//
//	int i = 0;
//	preorder(root, a, &i);
//
//	return a;
//
//}


//另一棵树的子树

//给你两棵二叉树 root 和 subRoot 。
//检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
//如果存在，返回 true ；否则，返回 false 。
//二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。
//tree 也可以看做它自身的一棵子树。
//法：让源树的每一棵子树跟目标树都比较一下
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
//{
//	if (root == NULL)
//		return false;
//
//	if (isSameTree(root, subRoot))
//		return true;
//
//	return isSubtree(root->left, subRoot)
//		|| isSubtree(root->right, subRoot);
//}


//二叉树遍历（创建）

//编一个程序，读入用户输入的一串先序（前序）遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 
//例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
//建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
//struct TreeNode
//{
//	struct TreeNode* left;
//	struct TreeNode* right;
//	char val;
//};
//struct TreeNode* CreateTree(char* a,int* pi)
//{
//	if (a[*pi] == '#')
//	{
//		(*pi)++;
//		return NULL;
//	}
//
//	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//	root->val = a[(*pi)++];
//	root->left = CreateTree(a, pi);
//	root->right = CreateTree(a, pi);
//
//	return root;
//};
//void InOrder(struct TreeNode*root)
//{
//	if (root == NULL)
//		return;
//	InOrder(root->left);
//	printf("%c ", root->val);
//	InOrder(root->right);
//}
//int main() {
//	char a[100];
//	scanf("%s", a);
//	int i = 0;
//	struct TreeNode* root = CreateTree(a, &i);
//	InOrder(root);
//	return 0;
//}


